package l.l.w.practice.BinaryTree;

import l.l.w.Instruction2Algorithm.MaximumSubarray.MaximumSubarray;

import javax.xml.crypto.dsig.keyinfo.RetrievalMethod;
import java.util.*;

/**
 * Created by llw on 2017/9/9.
 * 学习二叉树。http://blog.csdn.net/luckyxiaoqiang/article/details/7518888
 */
public class BinaryTreeLearn {
    //=========================求二叉树中的节点个数====================================
    public static int getNodeNum(BinaryTreeNode root){
        if(root == null) return 0;
        return getNodeNum(root.left) + getNodeNum(root.right) +1;
    }
    //==================================================================================
    //==================================求二叉树的深度==================================
    public static int getTreeDeepth(BinaryTreeNode root){
        if(root == null) return 0;
        return Math.max(getTreeDeepth(root.left),getTreeDeepth(root.right))+1;
    }
    //==================================================================================
    //===============================前序遍历(直接输出，不保存在数组或者链表中)使用递归==================================
    public static void preOrderSearchNoSave(BinaryTreeNode root){
        if(root == null) return;
        System.out.print(root.value+" ");
        preOrderSearchNoSave(root.left);
        preOrderSearchNoSave(root.right);
    }
    //===============================前序遍历(直接输出，不保存在数组或者链表中)不使用递归==================================
    public static void preOrderSearch(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            BinaryTreeNode node = stack.pop();
            System.out.print(node.value+ " ");
            if(node.right != null) stack.push(node.right);
            if(node.left != null) stack.push(node.left);
        }
        System.out.println();
    }
    //===============================前序遍历(保存在链表中)==================================
    public static List<Integer> preOrderSearchSaveInList(BinaryTreeNode root){
        LinkedList<Integer> list = new LinkedList<>();
        preOrderSearchSaveInList(root,list);
        return list;
    }
    private static void preOrderSearchSaveInList(BinaryTreeNode root, LinkedList<Integer> list) {
        if(root == null) return;
        list.add(root.value);
        preOrderSearchSaveInList(root.left,list);
        preOrderSearchSaveInList(root.right,list);
    }
    //=================================================================================================
    //===============================前序遍历(保存在数组中)==================================
    public static int[] preOrderSearchSaveInArray(BinaryTreeNode root){
        int nodeNum = getNodeNum(root);
        int[] result = new int[nodeNum];
        int i = 0;
        preOrderSearchSaveInArray(root,result,i);
        return result;
    }
    private static int preOrderSearchSaveInArray(BinaryTreeNode root, int[] result, int i) {
        if(root == null) return i;
        result[i++] = root.value;
        i = preOrderSearchSaveInArray(root.left,result,i);
        i = preOrderSearchSaveInArray(root.right,result,i);
        return i;
    }
    //===============================中序遍历(不保存) 使用递归==================================
    public static  void inOrderSearchNoSave(BinaryTreeNode root){
        if(root == null) return;
        inOrderSearchNoSave(root.left);
        System.out.print(root.value+" ");
        inOrderSearchNoSave(root.right);
    }

    //===============================中序遍历(不保存) 不使用递归==================================
    public static  void inOrderSearch(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode node = root;
        while(!stack.isEmpty() || node != null){ //！！！！注意这里的判断条件 ！！！处理右子树时，根需要先弹出来的，所以栈可能为空
            if(node != null){
                stack.push(node);
                node = node.left;
            }else{
                BinaryTreeNode n = stack.pop();
                System.out.print(n.value + " ");
                node = n.right;
            }
        }
        System.out.println();
    }
    //===============================中序遍历(保存在数组)==================================
    public static int[] inOrderSearchSaveInArray(BinaryTreeNode root){
        int num = getNodeNum(root);
        int[] result = new int[num];
        int i = 0;
        inOrderSearchSaveInArray(root,result,i);
        return result;
    }
    private static int inOrderSearchSaveInArray(BinaryTreeNode root, int[] result, int i) {
        if(root == null) return i;
        i = inOrderSearchSaveInArray(root.left, result, i);
        result[i++] = root.value;
        i = inOrderSearchSaveInArray(root.right,result,i);
        return i;
    }
    //===============================后序遍历 使用 递归==================================
    public static void postOrderSearchNoSave(BinaryTreeNode root){
        if(root == null) return;;
        postOrderSearchNoSave(root.left);
        postOrderSearchNoSave(root.right);
        System.out.print(root.value + " ");
    }

    //===============================后序遍历 不使用递归 使用两个栈==================================
    /**
     * 后序遍历的顺序为 左右中，前序遍历的顺序为 中左右，但是我们能够很容易的得到 中右左的顺序，然后将其颠倒即可。
     * @param root
     */
    public static void postOrderSearch(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        Stack<BinaryTreeNode> inverseStack = new Stack<>();
        while(!stack.isEmpty()){
            BinaryTreeNode node = stack.pop();
            inverseStack.push(node);
            if(node.left!= null){
                stack.push(node.left);
            }
            if(node.right!= null){
                stack.push(node.right);
            }
        }
        Iterator<BinaryTreeNode> iterator = inverseStack.iterator();
        while (iterator.hasNext()){
            BinaryTreeNode node = iterator.next();
            System.out.print(node.value + " ");
        }
        System.out.println();
        while (!inverseStack.isEmpty()){
            BinaryTreeNode node = inverseStack.pop();
            System.out.print(node.value + " ");
        }
        System.out.println();
    }
//================错了！！！！！！
    public static void postOrderSearchNoExtraStack1(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode p = root;
        BinaryTreeNode pre = null;
        while(!stack.isEmpty() || p != null){
            if( p != null ){
                stack.push(p);
                p = p.left;
            }else{
                BinaryTreeNode node = stack.peek();
                if(pre == node.right){
                    //如果是pre是右孩子，则弹出栈顶元素，即访问当前元素，并更新pre
                    pre = stack.pop();
                    System.out.println(pre.value);
                }else if(pre == node.left){
                    //如果pre是左孩子，则不弹出栈顶元素，访问右孩子。
                    // 因为pre默认为null，后序遍历访问的第一个元素左右孩子肯定都为空
                    // 所以先判断是否为右孩子，再判断是否为左孩子。
                    p = node.right;
                }else{
                    pre = null;
                }
            }
        }
    }


    //===============================后序遍历 不使用递归 使用1个栈==================================
    public static void postOrderSearchNoExtraStack(BinaryTreeNode root){
        BinaryTreeNode pre = root;
        BinaryTreeNode curr;
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            curr = stack.peek();
            if(pre != curr.left && pre != curr.right && curr.left!=null){
                stack.push(curr.left);
            }else if(pre != curr.right && curr.right != null){
                stack.push(curr.right);
            }else{
                pre =stack.pop();
                System.out.print(pre.value + " ");
            }
        }
        System.out.println();
    }
    //===========================分层遍历二叉树（按层次从上往下，从左往右）使用队列================
    public static void searchInLevel(BinaryTreeNode root){
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            BinaryTreeNode node = queue.poll();
            System.out.print(node.value + " ");
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
    }

    //===========================分层遍历二叉树（按层次从上往下，从左往右）不是使用队列================
    public static void searchInLevelNoQueue(BinaryTreeNode root){
        for(int i =0;;++i){
            if(searchOneLevel(root,i)==0) break;
        }
    }
    private static int searchOneLevel(BinaryTreeNode root, int i) {
        if(i==-1 || root == null){
            return 0;
        }
        if(i==0 ){
            System.out.print(root.value +" ");
            return 1;
        }
        return searchOneLevel(root.left,i-1)+searchOneLevel(root.right,i-1);
    }


    /**
     * 二叉树中的最大二叉搜索子树
     * @param root
     * @return
     */
    public static BinaryTreeNode 二叉树中的最大二叉搜索子树(BinaryTreeNode root){
        int[] record = new int[3];
        return getSubBinarySearchTree(root,record);
    }
    private static BinaryTreeNode getSubBinarySearchTree(BinaryTreeNode root, int[] record) {
        if(root == null) {
            record[0]=0;//size
            record[1]= Integer.MAX_VALUE;//min      表示当前子树的最小值整型的最大值
            record[2]=Integer.MIN_VALUE;//max
            return null;
        }
        BinaryTreeNode left = getSubBinarySearchTree(root.left, record);
        int lsize = record[0];
        int lmin = record[1];
        int lmax = record[2];
        BinaryTreeNode right = getSubBinarySearchTree(root.right, record);
        int rsize = record[0];
        int rmin = record[1];
        int rmax = record[2];
        if(left == root.left && right == root.right && lmax < root.value && rmin > root.value){//这里表示 两天的最大搜索二叉子树可以与当前节点连接
            record[0] = lsize + rsize +1;       //这个地方需要添加 root的节点
            record[1] = lmin;
            record[2] = rmax;
            return root;
        }//若不能连接，则选择最大的搜索子树返回
        if(lsize > rsize){
            record[0] = lsize;
            record[1] = lmin;
            record[2] = lmax;
            return  left;
        }else{
            record[0] = rsize;
            record[1] = rmin;
            record[2] = rmax;
            return  right;
        }
    }

    /**
     * 未排序数组中累加和为指定值的最长子数组（有正有负）
     * @param array
     * @param k
     * @return
     */
    public static int longestSubArraySumProvidedByUser(int[] array, int k){
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,0);
        int sum =0;
        int maxLength=0,start=-1,end=-1;
        for(int i = 0; i < array.length; ++i){
            sum+=array[i];
            if(map.containsKey(sum-k)){
                int length = i - map.get(sum-k);
                if(length > maxLength){
                    maxLength = length;
                    start=map.get(sum-k)+1;
                    end = i;
                }
            }if(!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
        return maxLength;
    }
    public static int longestDistanceSubBinaryTree(BinaryTreeNode root){
        int[] record = new int[2];
        longestDistanceSubBinaryTree(root,record);
        return record[0];
    }

    private static void longestDistanceSubBinaryTree(BinaryTreeNode root, int[] record) {
        if(root == null) {
            record[0]=0;
            record[1]=0;
            return ;
        }
        longestDistanceSubBinaryTree(root.left, record);
        int lLength = record[0];
        int lenFromLeft = record[1];
        longestDistanceSubBinaryTree(root.right, record);
        int rLength = record[0];
        int lenFromRight = record[1];
        record[1] = Math.max(lenFromLeft,lenFromRight)+1;
        int curNodemax = lenFromLeft + lenFromRight +1;
        record[0] = Math.max(Math.max(lLength,rLength),curNodemax);
    }

    //===========================================================================
    public static void printTree(BinaryTreeNode root){
        int deepth = getTreeDeepth(root);
        for(int i=0;i < deepth; ++i){
            int numOfSpace = (1<<(deepth-i))+(1<<(deepth-i-1));
            printOneLevel(root,i,numOfSpace);
            System.out.println();
        }
    }
    private static void printOneLevel(BinaryTreeNode root, int i, int numOfSpace) {
        if(i == -1 || root == null){
            for (int j = 0; j < numOfSpace; ++j){
                System.out.print(" ");
            }
            System.out.print(" ");
            for (int j = 0; j < numOfSpace; ++j){
                System.out.print(" ");
            }
            return;
        }
        if(i ==0){
            for (int j = 0; j < numOfSpace; ++j){
                System.out.print(" ");
            }
            System.out.print(root.value);
            for (int j = 0; j < numOfSpace; ++j){
                System.out.print(" ");
            }
            return;
        }
        printOneLevel(root.left,i-1,numOfSpace);
        printOneLevel(root.right,i-1,numOfSpace);
    }


    public static void main(String[] args) {
        BinaryTreeNode root = constructTree();
//        System.out.println("nodeNum: "+getNodeNum(root));
//        System.out.println("treeDeepth: "+getTreeDeepth(root));
//        preOrderSearchNoSave(root);
//        System.out.println();

//        preOrderSearch(root);
//        inOrderSearch(root);
//        postOrderSearch(root);
        postOrderSearchNoExtraStack(root);
        System.out.println("======");
        postOrderSearchNoExtraStack1(root);
//        List<Integer> result = preOrderSearchSaveInList(root);System.out.println(result);
//        int[] resultArray = preOrderSearchSaveInArray(root);System.out.println(Arrays.toString(resultArray));
//        inOrderSearchNoSave(root);System.out.println();
//        int[] inOrderArray = inOrderSearchSaveInArray(root);System.out.println(Arrays.toString(inOrderArray));
//        postOrderSearchNoSave(root);System.out.println();
//        searchInLevel(root);System.out.println();
//
//        searchInLevelNoQueue(root);System.out.println();
//
//        printTree(root);
    }
    public static BinaryTreeNode constructTree(){
        BinaryTreeNode root = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node7 = new BinaryTreeNode(7);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node6 = new BinaryTreeNode(6);
        BinaryTreeNode node8 = new BinaryTreeNode(8);

        root.left=node2;
        root.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node4.right = node7;
        node6.left = node8;
        return root;
    }
}

class BinaryTreeNode{
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
    BinaryTreeNode(int value){
        this.value = value;
    }
}